package search.fitnessfunctions;

import java.util.HashMap;
import java.util.Stack;
import primitives.cluster.ClusterHead;
import primitives.cluster.ClusterNode;
import primitives.cluster.IClusterLevel;
import primitives.graph.Graph;
import primitives.graph.Node;
import primitives.graph.Transition;

/**
 *
 * @author mat
 */


public class LutzFitnessFunction extends TreeFitnessFunction {

	@Override
	public double evaluate(ClusterHead result) {
		Stack<ClusterNode> toVisit = new Stack<ClusterNode>();
		toVisit.push(result);
		double ret = 0;
		
		Graph g = new Graph();
		for(Node n : result.getNodes()){
			g.addNode(n);
		}
		
		while(!toVisit.isEmpty()){
			ClusterNode current = toVisit.pop();
			ret += calculateComplexity(current, g,  result);
			
		}
		
		if(ret == 0){
			return Double.MAX_VALUE;
		}else{
			return ret;
		}
	}
	
	
	
	
	
	private static double calculateComplexity(ClusterNode container, Graph g, ClusterHead ch){
		double ret = 0;
		//NUMBER OF NODES IN CLUSTER
		ret += container.getNodesInLeaves().size() + 1;
		
		//NUMBER OF MODULES IN CLUSTER
		for(IClusterLevel icl : container.getChildren()){
			if(icl.encapsulates()) ret++;
		}
		ret++;
		
		//NAME OF EACH ENTITY
		HashMap<IClusterLevel, Double> f_values = new HashMap<IClusterLevel, Double>();
		double F = 0;
		
		// calculate number of bits needed based on in-degree of:
		for(IClusterLevel icl : container.getChildren()){
			if(icl.encapsulates()){
				//modules:
				double f_m = f((ClusterNode)icl, g);
				f_values.put(icl, f_m);
				F += f_m;
			}else{
				//nodes;
				Node n;
				n = icl.getNodes().toArray(new Node[1])[0];
				double f_n = f(n,g);
				f_values.put(icl,f_n);
				F += f_n;
			}
		}
		
		for(IClusterLevel icl : f_values.keySet()){
			double f = f_values.get(icl);
			ret += l(-Math.log(f/F)	) - f * Math.log(f/F);	
		}
		
		//HIERARCHY ENCODING
		for(Node n : container.getNodesInLeaves()){
			for(Node nP : n.getTransitionsAsN()){
				ret += l(relativeDepth(container, lowestCommonAncestor(n,nP, ch), ch));
				
				
			}
			
		}
		return ret;
	}
	
	
	
	/** Calculating the number of times module/node n will be referred to **/
	private static int f(Node n, Graph g){
		return indegree(n,g) + 1;
	}
	
	private static int f(ClusterNode container, Graph g){
		int indegree = 0;
		for(Node n : container.getNodesInLeaves()){// This assumes you need indegree of all children - not just immediates.
			indegree += indegree(n,g);
		}
		return indegree +1;
	}
	
	private static int indegree(Node n, Graph g){
		
		int indegree = 0;
		for(Node current : g.getNodes()){
			for(Transition t : current.getTransitionsAsT()){
				if(t.getDestinationNode() == n){
					indegree++;
				}
				
			}
		}
		return indegree;
	}
	
	/** Prefix stuff **/
	private static double l(double n){
		return 1 + log2(n) + 2 * log2(log2(n+1)) + 1;
		
	}
	private static double l(int n){
		return 1 + log2(n) + 2 * log2(log2(n+1)) + 1;
		
	}
	private static double log2(int n){
		return Math.log(n) / Math.log(2);
	}
	private static double log2(double n){
		return Math.log(n) / Math.log(2);
		
	}
	
	private static int relativeDepth(IClusterLevel a, IClusterLevel b, ClusterHead tree){
		int depthA = -1;
		int depthB = -1;
		
		Stack<SearchPair> stack = new Stack<SearchPair>();
		stack.push(new SearchPair(0, tree));
		
		while(!stack.isEmpty()){
			SearchPair current = stack.pop();
			
			if(current.item == a){
				depthA = current.depth;
			}
			if(current.item == b){
				depthB = current.depth;
			}
			if(current.item.encapsulates()){
				ClusterNode cast = (ClusterNode)current.item;
				for(IClusterLevel c : cast.getChildren())
						stack.push(new SearchPair(current.depth+1, c));
			}
			
			
		}
		assert(depthA != -1);
		assert(depthB != -1);
		return Math.abs(depthA - depthB);
	}
	
	private static IClusterLevel lowestCommonAncestor(Node n1, Node n2, IClusterLevel tree){
		Stack<IClusterLevel> toLookAt = new Stack<IClusterLevel>();
		toLookAt.push(tree);
		IClusterLevel deepest = tree;
		while(!toLookAt.isEmpty()){
			IClusterLevel current = toLookAt.pop();
			if(!current.encapsulates()) continue;
			ClusterNode cast = (ClusterNode)current;
			if(current.contains(n1) && current.contains(n2)){
				deepest = current;
				for(IClusterLevel c : cast.getChildren())
					toLookAt.push(c);
			}
			
			
		}
		return deepest;
	}
	
	
}
class SearchPair{
		int depth;
		IClusterLevel item;
		public SearchPair(int d, IClusterLevel t){
			depth = d;
			item = t;
		}
}